import java.util.ArrayList;
import java.util.List;

/**
 * @author tmh
 * @date 2024/9/27 22:41
 * @description
 */
public class T22括号生成 {
    public static void main(String[] args) {
        generateParenthesis(2);
    }
    private final static List<String> result = new ArrayList<>();

    public static List<String> generateParenthesis(int n) {
        dfs(0,0,n,"");
        return result;
    }

    private static void dfs(int left, int right, int n, String s) {
        if (left == n && right == n) {
            result.add(s);
            return;
        }
        //先添加做括号，再添加右括号，直观的思路
        if (left < n) {
            dfs(left + 1, right, n, s + "(");
        }
        if (right < left) {
            dfs(left, right + 1, n, s + ")");
        }
    }
}
